The problem can be found at the following link: Question Link
To solve this question and count the number of subarrays, I maintaining a window [i, j]
such that all elements in the window are in the range [L, R]
. Then, I iterate through the array.
- For each element
a[j]
, I check if it falls within the specified range. If it does, I update therange
of window and continue. Ifa[j]
is greater thanR
, I reset therange
of window and update the starting indexi
toj + 1
. The count is updated with the currentrange
value at each step.
- Time Complexity: O(N), where N is the number of elements in the array.
- Auxiliary Space Complexity:
O(1)
, as no extra space is used.
class Solution{
public:
long countSubarrays(int a[], int n, int L, int R)
{
long out = 0, range = 0;
long i = 0;
for (long j = 0; j < n; ++j)
{
if (a[j] >= L && a[j] <= R)
range = j - i + 1;
else if (a[j] > R)
range = 0, i = j + 1;
out += range;
}
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.